package bin_tree;

import com.sun.javafx.scene.NodeHelper;
import oj.TreeNode;

import javax.xml.soap.Node;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MyBinaryTree {
    //孩子表示法
    private static class Node {
        private char val;   //数据域
        private Node left;  //左孩子的引用，常代表左孩子为根的整棵左子树
        private Node right; //右孩子的引用，常代表右孩子为根的整棵右子树

        public Node(char val) {
            this.val = val;
        }
    }

    //生成一个测试树
    public Node buildTree(){
        Node nodeA=new Node('A');
        Node nodeB=new Node('B');
        Node nodeC=new Node('C');
        Node nodeD=new Node('D');
        Node nodeE=new Node('E');
        Node nodeF=new Node('F');
        Node nodeG=new Node('G');
        Node nodeH=new Node('H');
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeE.right=nodeH;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        return nodeA;
    }

    /**
     * 先序遍历，传入一个根节点，就可以按照先序遍历的顺序进行遍历（根左右）
     * @param root
     */
    public void preOrder(Node root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
}

    /**
     * 中序遍历  传入一个根节点，就可以按照中序遍历（左根右）的顺序进行遍历
     * @param root
     */
    public void inOrder(Node root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    /**
     * 后序遍历，传传入一个根节点就可以按照后序遍历（左右根）的顺序进行遍历
     * @param root
     */
    public void postOrder(Node root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * 获取结点总数
     * @param root
     * @return
     */
    public int getNodeSize(Node root){
        if(root==null){
            return 0;
        }
        return 1+getNodeSize(root.left)+getNodeSize(root.right);
    }

    /**
     * 获取叶子结点的个数
     * @param root
     * @return
     */
    public int getLeafNodeCount(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null && root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    /**
     * 求二叉树的高度
     */
    public int getHeight(Node root){
        if(root==null){
            return 0;
        }
        return 1+Math.max(getHeight(root.right),getHeight(root.left));
    }

    /**
     * 在二叉树中查看一个值是否存在
     * @param root
     */
    public boolean contains(Node root,char val){
        if(root==null){
            return false;
        }
        if(root.val==val){
            return true;
        }
        return contains(root.left,val) || contains(root.right,val);
    }

    /**
     * 求二叉树第K层的节点个数
     * @param root
     */
    public int getSingelNode(Node root,int k){
        if(k<=0 || root==null){//不合法
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getSingelNode(root.left,k-1)+getSingelNode(root.right,k-1);
    }

    /**
     * 层序遍历
     * @param root
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret=new LinkedList<>();
        if(root==null){
            return ret;
        }
        Queue<Node> queue=new LinkedList<>();//使用LinkedList由于我们要频繁的进行插入和删除操作
        queue.offer(root);
        while (!queue.isEmpty()) {
            List level=new LinkedList();
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                Node cur=queue.poll();
                level.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(level);
        }
        return ret;
    }




    public static void main(String[] args) {
        MyBinaryTree myBinaryTree=new MyBinaryTree();
        Node root=myBinaryTree.buildTree();
        System.out.print("先序遍历的结果："+" ");
        myBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("---------");
        System.out.print("中序遍历的结果："+" ");
        myBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("---------");
        System.out.print("后序遍历的结果："+" ");
        myBinaryTree.postOrder(root);
        System.out.println();
        System.out.println("二叉树节点个数为：");
        System.out.println(myBinaryTree.getNodeSize(root));
        System.out.println("二叉树的叶子节点个数为：");
        System.out.println(myBinaryTree.getLeafNodeCount(root));
        System.out.println("二叉树的高度为：");
        System.out.println(myBinaryTree.getHeight(root));
        System.out.println(myBinaryTree.contains(root,'A'));
        System.out.println(myBinaryTree.contains(root,'M'));
        System.out.println(myBinaryTree.getSingelNode(root,2));
        System.out.print("层序遍历的结果:"+" ");
        System.out.println(myBinaryTree.levelOrder(root));

    }
}